\section{Memoised Garbage Collection}
\begin{frame}{Memoised Garbage Collection}
% short overview on what MGC is, before explaining details
\begin{itemize}
\item Mark and Sweep traverses all vertices in a graph.
\item Memoised Garbage Collection tries to evaluate only the part that has changed.
\item An Incremental Shortest Path algorithm is used to determine which parts have been modified.
\end{itemize}
\end{frame}

%2ab
\begin{frame}{Incremental Shortest Path}
The depth of the red nodes have changed in the second graph, but have not yet been updated.
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S] {$v_1$};
  \node[state] (v2) [label=15:2, right of=v1] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v2) edge (v3)
    (v3) edge (v6)
    (v4) edge (v5)
  ;
\end{tikzpicture} 
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S] {$v_1$};
  \node[state] (v2) [label=15:2, right of=v1, fill=red] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2, fill=red] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture}
\end{figure}
\end{frame}

\begin{frame}{Ramalingam and Reps' algorithm}
\begin{itemize}
\item Determine the set of vertices whose depth has (likely) changed. \pause
\item \emph{depth($u$)} indicates the \emph{stored} depth of vertex $u$. \pause
\item Storing the depth is the memoisation part of the algorithm. \pause
\item Ramalingam and Reps algorithm uses the right-handside function $rhs(G',u) = min_{v \in Pred(G',u)} depth(v) +1$ . \pause
\item A vertex $u \in V'$ is inconsistent if $rhs(G',u) \neq depth(u)$.
\end{itemize}
\end{frame}

%2ab
\begin{frame}{Ramalingam and Reps' algorithm}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S] {$v_1$};
  \node[state] (v2) [label=15:2, right of=v1] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v2) edge (v3)
    (v3) edge (v6)
    (v4) edge (v5)
  ;
\end{tikzpicture} 
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S] {$v_1$};
  \node[state] (v2) [label=15:2, right of=v1, fill=red] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2, fill=red] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture}
\end{figure}

Inconsistent vertices are traversed according to their key:\\$key(G',u) = min(rhs(G',u),depth(u))$ .
\end{frame}

%a
\begin{frame}{Memoised Garbage Collection}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:2, right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2, fill=green] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4, fill=green] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=green] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v2) edge (v3)
    (v3) edge (v6)
    (v4) edge (v5)
  ;
\end{tikzpicture} 
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:2, right of=v1, fill=red] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2, fill=red] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture} \\
\tiny \emph{Label}: depth, \emph{green}: consistent, \emph{transparant}: unvisited, \emph{red}: inconsistent. \normalsize
\end{figure}
\end{frame}

%b
\begin{frame}{Memoised Garbage Collection}
\begin{center}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:2, right of=v1, fill=red] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2, fill=red] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:1, right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2, fill=red] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture} \\
\tiny \emph{Label}: depth, \emph{green}: consistent, \emph{transparant}: unvisited, \emph{red}: inconsistent. \normalsize
\end{center}
\end{frame}
%c
\begin{frame}{Memoised Garbage Collection}
\begin{center}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:1, right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [label=15:3, right of=v2, fill=red] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:1, right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [label=15:$\infty$, right of=v2] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture} \\
\tiny \emph{Label}: depth, \emph{green}: consistent, \emph{red}: inconsistent. \normalsize
\end{center}
\end{frame}
%d
\begin{frame}{Memoised Garbage Collection}
\begin{center}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:1, right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [label=15:$\infty$, right of=v2] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4] {$v_5$};
  \node[state] (v6) [label=15:3, right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:1, right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [label=15:$\infty$, right of=v2] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4, fill=green] {$v_5$};
  \node[state] (v6) [label=15:2, right of=v5, fill=green] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture} \\
\tiny \emph{Label}: depth, \emph{green}: consistent, \emph{red}: inconsistent. \normalsize
\end{center}
\end{frame}
%e
\begin{frame}{Memoised Garbage Collection}

\begin{center}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:1, right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [label=15:$\infty$, right of=v2] {$v_3$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4, fill=green] {$v_5$};
  \node[state] (v6) [label=15:2, right of=v5, fill=green] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
    (v3) edge (v6)
  ;
\end{tikzpicture}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]

  \node (S)                    {};
  \node[state] (v0) [label=15:0, right of=S, fill=green] {$v_0$};
  \node[state] (v1) [label=15:1, below of=S, fill=green] {$v_1$};
  \node[state] (v2) [label=15:1, right of=v1, fill=green] {$v_2$};
  \node[state] (v4) [label=15:2, below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [label=15:3, right of=v4, fill=green] {$v_5$};
  \node[state] (v6) [label=15:2, right of=v5, fill=green] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v0) edge (v2)
    (v1) edge (v4)
    (v2) edge (v6)
    (v4) edge (v5)
  ;
\end{tikzpicture} \\
\tiny \emph{Label}: depth, \emph{green}: consistent, \emph{red}: inconsistent. \normalsize
\end{center}
\end{frame}

\begin{frame}{Time Complexity}
\begin{itemize}
\item The time-complexity of Mark and Sweep is linear to the size of the heap. \pause
\item The time-complexity of MGC is in terms of the size of affected objects. \pause
\item The extended size of an object $o$ is $|Pred(o)|$. \pause
\item Let $N$ the sum of extended sizes of affected objects and $M$ the cost to calculate $rhs$.
\item Worst-case time-complexity: $O(N (log(N) + M))$ .
\end{itemize}
\end{frame}
